package algorithm;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author: vince_zww
 * @date: 2019/9/11 17:01
 * @desceription: 桶位排序
 */
public class BucketSort {
    public static void main(String[] args) {
        int a[]={99,9,6,8,10,2,5,3,4,7,12,15,48,78,95,35,23,29,98,19};

        long bucketSort_1StartTime = System.nanoTime();
        System.out.println(Arrays.toString(bucketSort_1(a)));
        long bucketSort_1EndTime = System.nanoTime();
        System.out.println("桶位排序写法1运行时间："+(bucketSort_1EndTime-bucketSort_1StartTime)+"ns");


        ArrayList<Integer> array=new ArrayList<Integer>();
        for (int i:a) {
            array.add(i);
        }
        long bucketSort_2StartTime = System.nanoTime();
        System.out.println(bucketSort_2(array,5).toString());
        long bucketSort_2EndTime = System.nanoTime();
        System.out.println("桶位排序写法2运行时间："+(bucketSort_2EndTime-bucketSort_2StartTime)+"ns");
    }

    /**
     * 桶位排序——写法1
     */
    private static int[] bucketSort_1(int[] souceArray){
        int[] arr = Arrays.copyOf(souceArray,souceArray.length);

        return sort_1(arr,5);
    }

    //事先确定桶数
    private static int[] sort_1(int[] arr,int bucketSize){
        if(arr.length <= 0){
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        //找到最大值和最小值
        for (int value:arr) {
            if (value<minValue){
                minValue = value;
            }else if(value>maxValue){
                maxValue = value;
            }
        }

        int bucketCount = (int)Math.floor((maxValue-minValue)/bucketSize)+1;
        int[][] buckets = new int[bucketCount][0];

        //利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i]-minValue)/bucketSize);
            buckets[index] = arrAppend(buckets[index],arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket:buckets) {
            if(bucket.length<=0){
                continue;
            }
            //对每个桶进行排序，调用快排 (这里依赖于其他排序算法,可以插入，选择，快排等)
            bucket = QuickSort.quickSort(bucket,0,bucket.length-1);
            for (int value:bucket) {
                arr[arrIndex++]=value;
            }
        }

        return arr;
    }
    /**
     * 扩容,并保存数据
     */
    private static int[] arrAppend(int[] arr,int value){
        arr = Arrays.copyOf(arr,arr.length+1);
        arr[arr.length-1] =value;
        return  arr;
    }



    /**
     * 桶位排序——写法2
     * 写法2运用了容器
     */
    public static ArrayList<Integer> bucketSort_2(ArrayList<Integer> array,int bucketSize){
        if(array == null || array.size() < 2){
            return array;
        }
        int max = array.get(0);
        int min = array.get(0);
        //找到最大值和最小值
        for (int i = 0; i < array.size(); i++) {
            if(array.get(i) > max){
                max = array.get(i);
            }else if(array.get(i) < min){
                min = array.get(i);
            }
        }

        int bucketCount = (max - min) / bucketSize + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
        ArrayList<Integer> resultArr = new ArrayList<>();
        //桶
        for (int i = 0; i < bucketCount; i++) {
            bucketArr.add(new ArrayList<Integer>());
        }
        for (int i = 0; i < array.size(); i++) {
            bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
        }
        for (int i = 0; i < bucketCount ; i++) {
            if(bucketCount == 1){
                bucketSize--;
            }
            ArrayList<Integer> temp = bucketSort_2(bucketArr.get(i),bucketSize);
            for (int j = 0; j < temp.size(); j++) {
                resultArr.add(temp.get(j));
            }
        }
        return resultArr;
    }


}
